Fuzzy Weirstrass theorem and convex fuzzy mappings

The convexity and continuity of fuzzy mappings are defined through a linear ordering and a metric on the set of fuzzy numbers. The local-global minimum property of real-valued convex functions is extended to convex fuzzy mappings. It is proved that a strict local minimizer of a quasiconvex fuzzy mapping is also a strict global minimizer. Characterizations for convex fuzzy mappings and quasiconvex fuzzy mappings are given. In addition, the Weirstrass theorem is extended from real-valued functions to fuzzy mappings.     

A new distributed approximation algorithm for constructing minimum connected dominating set in wireless ad hoc networks

In recent years, constructing a virtual backbone by nodes in a connected dominating set (CDS) has been proposed to improve the performance of ad hoc wireless networks. In general, a dominating set satisfies that every vertex in the graph is either in the set or adjacent to a vertex in the set. A CDS is a dominating set that also induces a connected sub‐graph. However, finding the minimum connected dominating set (MCDS) is a well‐known NP‐hard problem in graph theory. Approximation algorithms for MCDS have been proposed in the literature. Most of these algorithms suffer from a poor approximation ratio, and from high time complexity and message complexity. In this paper, we present a new distributed approximation algorithm that constructs a MCDS for wireless ad hoc networks based on a maximal independent set (MIS). Our algorithm, which is fully localized, has a constant approximation ratio, and O(n) time and O(n) message complexity. In this algorithm, each node only requires the knowledge of its one‐hop neighbours and there is only one shortest path connecting two dominators that are at most three hops away. We not only give theoretical performance analysis for our algorithm, but also conduct extensive simulation to compare our algorithm with other algorithms in the literature. Simulation results and theoretical analysis show that our algorithm has better efficiency and performance than others. Copyright © 2005 John Wiley & Sons, Ltd.     

Algebraic properties of cryptosystem PGM

In the late 1970s Magliveras invented a private-key cryptographic system calledPermutation Group Mappings (PGM). PGM is based on the prolific existence of certain kinds of factorization sets, calledlogarithmic signatures, for finite permutation groups. PGM is an endomorphic system with message space ℤ_|G| for a given finite permutation groupG. In this paper we prove several algebraic properties of PGM. We show that the set of PGM transformations ℐ _G is not closed under functional composition and hence not a group. This set is 2-transitive on ℤ_|G| if the underlying groupG is not hamiltonian and not abelian. Moreover, if the order ofG is not a power of 2, then the set of transformations contains an odd permutation. An important consequence of these results is that the group generated by the set of transformations is nearly always the symmetric group ℒ_|G|. Thus, allowing multiple encryption, any permutation of the message space is attainable. This property is one of the strongest security conditions that can be offered by a private-key encryption system. S. S. Magliveras was supported in part by NSF/NSA Grant Number MDA904-82-H0001, by U.S. West Communications, and by the Center for Communication and Information Science of the University of Nebraska.     

无线传感器网络中d-Hop 2-连通容错支配集的分布式构造算法

无线传感器网络随节点移动组成自我维持的自组织系统,采用连通支配集的虚拟骨干技术可使平面网络系统层次化而简化节点路由、管理和维护。但大规模无线传感器网络的连通支配集节点数目依然庞大,d-hop连通支配集可以大大减小支配集节点数目。另外,由于存在节点失效、链路断裂等无线特性,虚拟骨干网需要具备一定的容错性。在单位圆盘图网络模型中为构建精简且具有容错能力的虚拟骨干网,提出d-hop 2-连通支配集的分布式构造算法,先构造d-hop独立支配集后再连通形成d-hop 2-连通支配集。并从理论和仿真上对算法的复杂度、近似比和算法性能作了进一步探讨和验证。     

无线自组网络中的基于多个支配集的路由协议*

提出了一种在无线自组网络中建立多个连通支配集,使其分时共同承担网络中继传输的方法,以防止部分节点被过度消耗,维持网络中能量消耗的平衡.仿真实验表明,基于多个连通支配集的路由方法可有效防止部分节点被过度消耗、维护网络的能量消耗平衡、延长网络的寿命.     

Rn 上的线性局部保控映射

设φ：Rn →Rn 是一个线性映射,对任意x∈Rn ,都存在与x有关的线性保控映射ψx ,使得φ（x）＝ψx（x）,则称φ是欧氏空间上的一个线性局部保控映射。线性保控映射是线性局部保控映射,其逆命题不成立。文中定义了两个与φ相关的Rn的子集Iφ和IIφ,如果任意Rn上的点都属于Iφ（或IIφ）,那么这个线性局部保控映射φ是线性保控映射。     

Perfect secret sharing scheme based on vertex domination set

Due to the fast development in data communication systems and computer networks in recent years, the necessity to protect the secret data has become extremely imperative. Several methods have been proposed to protect the secret data; one of them is the secret sharing scheme. It is a method of distributing a secret K among a finite set of participants, in such a way that only predefined subset of participant is enabled to reconstruct a secret from their shares. A secret sharing scheme realizing uniform access structure described by a graph has received a considerable attention. In this scheme, each vertex represents a participant and each edge represents a minimum authorized subset. In this paper, an independent dominating set of vertices in a graph G is introduced and applied as a novel idea to construct a secret sharing scheme such that the vertices of the graph represent the participants and the dominating set of vertices in G represents the minimal authorized set. While most of the previous schemes were based on the principle of adjacent vertices, the proposed scheme is based upon the principle of non-adjacent vertices. We prove that the scheme is perfect, and the lower bound of the information rate of this new construction is improved when compared to some well-known previous constructions. We include an experiment involving security threats to demonstrate the effectiveness of the proposed scheme.     

一种基于反向CDS树的异构WSNs拓扑构建方法

在无线传感器网络中,拓扑控制是节约能源、延长生命周期的一项关键技术。现有拓扑控制方法的研究主要集中在同构网络,对此,面向异构网络提出了一种低信息复杂度的基于反向连通支配集树的分布式拓扑构建算法。基于最小连通支配集构建虚拟骨干树,改进了A3G算法中节点的适应度函数和算法流程,优化了产生的连通支配集的规模和通信开销,进一步降低信息复杂度,在保证连通性的同时关闭网络冗余节点以降低能耗。理论分析和仿真实验证明,算法能够以较小的时间和通信代价构建拓扑,延长网络生命周期。     

无线传感网络中能量均衡的连通支配集算法

连通支配集是无线传感器网络中构建虚拟骨干网络的重要手段.由于支配集中节点的能耗相对其他节点要多,支配集中剩余能量较小的节点决定了虚拟骨干网的生命周期.现有算法或者只是关注构造较小的支配集,或者没有考虑调整能耗极快的支配节点.提出了一种能量均衡的连通支配集算法,基于节点剩余能量和连通度构造支配集,在网络运行过程中根据耗能速度,提前选择候选支配节点,分流负载过重的支配节点.仿真结果表明,新算法能以较小消息开销,有效延长网络寿命.     

无线传感器网络中的连通支配集求解算法

连通支配集在无线传感器网络中有着重要的作用,通过对连通支配集的深入分析得到了关于连通支配集的一个新特性,即最小连通支配集是图的一棵包含最多叶子节点的生成树中的非叶子节点的集合。根据这个结论设计了一种全新的连通支配集求解算法,即通过建立一棵含叶子节点较多的生成树来寻找一个较小的连通支配集。仿真实验表明,新算法较前人的算法有明显的改进。